Project 1 -- EECS 281 -- Fall 2009

<(^-^)> Kirby's Quest for Cake <(^-^)>

Design Plan Due: Monday, September 28th at 11:59:59pm

Project Due: Friday, October 2nd at 6:00:00pm

Updates (from original version)

Clarified input/output directions - only use stdin (cin) and stdout (cout)
Imposed memory limitation of O(N)
modified timer class coce
changed unoccupied spaces from ' ' to '.' for clarity

Honor Code

As with any project/homework/exam in this class, you must abide by The Engineering Honor Code. Remember, all work submitted should only be work done by you and only you. If you are unsure about the level of allowed collaboration, please consult Professor Markov, the GSIs, or the IAs.

Overview

For this project, you will write a C++ program to help Kirby through a maze to find his reward: a piece of delicious cake (not a lie).

Evaluation

The quality of your guiduance will be graded on correctness, runtime, and coding style. A more detailed breakdown is described below under "Grading".

The Maze

The maze (overhead view) consists of:
1) open (walkable) areas, denoted by '.'
2) walls (non-walkable) areas, denoted by '@'
3) Kirby's starting position (K)
4) the location of the cake (C)

Unfortunately, Kirby is weak from hunger, so he cannot fly and can only move in the North, South, East, or West directions. That is, he may not travel along the diagonals of the maze. Your job is to find a route for Kirby to his cake and mark this route with the '+' symbol. For instance, a simple maze might look like:

@@@@@@@
@@C...@
@...@@@
@.....@
@@@@@.@
@K....@
@@@@.@@

while the solution might look like:

@@@@@@@
@@C...@
@.+.@@@
@.++++@
@@@@@+@
@K++++@
@@@@.@@

Specifications

Kirby will be confined to a rectangular maze that is M rows by N columns, i.e., Kirby knows the cake is somewhere within the maze and will not leave the premises. Other sample mazes have been posted on CTools as well as in the eecs281 directory in the AFS space.

Routing Approaches

You will develop three routing approaches for Kirby:
1) Find any valid path using a queue
2) Find any valid path using a stack
3) Find an optimal (shortest distance) path

Queue-based Approach

First, enqueue Kirby's start position and then do the following:

dequeue the next location.
enqueue all of the walkable tiles ('.') immediately North, South, East, and West (in that order) of the location you just dequeued that have never before been enqueued.
Check to see if any of these spaces hold the cake. If none of them do, go back to Step 1. Remember: Kirby cannot move diagonally, so spaces to the Northwest, Northeast, Southwest, and Southest are not considered next to each other and should not be enqueued in this step.
Once you have found the cake, you still need to guide Kirby to the cake. Remember, Kirby is hungry and therefore does not want to visit the same square twice. That is, the path you give to Kirby should not contain any loops or backtrack onto itself.

Stack-based Approach

This will be similar to the queue-based approach except that you will push and pop the locations instead of enqueue and dequeue them. Note that the approaches given are high-level so you will need to expand upon them to finish this project.

Optimal Path Approach

You are free to use any routing approach you wish, provided that it is faster than the sum of the runtimes of the queue- and stack-based approaches. Example approaches can be the queue and stack-based approaches described above, a combination of both, or something completely different. Regardless of what you implement, Kirby must reach his cake in as few spaces as possible. Note: You will be graded on how many test cases are solved correctly within a (generous) set time limit. No partially credit will be given to solutions that are disconnected, go through walls, leaving the maze, or include any illegal moves. You will also be reward for finishing quickly, provided that you have passed all the testcases.

Input and Output Formats

There are two input formats. The first is the text-based map (shown in the example above). The second is a coordinate-based system where Kirby (K), the cake (C), and each wall (@) location are listed by its row and column position (in that order). Every other location (unspecified) is assumed to be empty ('.'). In both cases, the size of the maze (M rows by N columns) is specified as a pair of integers, separated by a single space, as the first line of the input file. That is, the first line of the file will be: M N. For example, the following is a legal input file using the text-map format:

5 4
@@@@
K.@C
@...
...@
@..@

and the coordinate-based format:

Simiarly, there are also two output formats. The first is the text-map format and must include:

the dimensions of the maze (M and N) as the first line
the original maze setup
the route that Kirby takes (+)

The second is the coordinate-based system, which only needs to include the locations of the route in the order at which Kirby travels. For example, given the sample input, a possible (correct) output in the text-map format would be:

5 4
@@@@
K+@C
@+++
...@
@..@

and in the coordinate-based format would be:

If a solution does not exist, i.e., there is no possible way for Kirby to eat, print "The cake is a lie." to standard error (stderr), exit(1), and leave the output file blank. To print the error message, use

cerr << "The cake is a lie." << endl;

For both input and output, use standard in (stdin) and standard out (stdout), respectively.

Reporting Runtime

To evaluate the amount of time your search algorithms need, use the following class (also discussed in lecture):

#include <sys/resource.h>
#include <sys/time.h>

class Timer
{  
  public:
    Timer() { getrusage(RUSAGE_SELF, &startu); }
  
  void stopTime()
  {
    getrusage(RUSAGE_SELF, &endu);
    double start_sec = startu.ru_utime.tv_sec + (double(startu.ru_utime.tv_usec)*1000000);
    double   end_sec =   endu.ru_utime.tv_sec + (double(  endu.ru_utime.tv_usec)*1000000);
    duration = end_sec - start_sec;
  }
  
  double getTime() { return duration; }  
  
  private struct rusage startu;
  private struct rusage endu;
  private double duration;
};

You must measure the time for the entire search algorithm, including figuring out what exact path is taken. Remember, do not include the time to read in the input or write the output. You are also not allowed to pre-compute/sort/search any of the input data. This will result in 0 points in the timing category (see below). All timing information should be reported as

Total Runtime: X seconds

to standard output, where X is a base-10 number representing the amount of time in seconds. Use the following command to do this:

 cout << endl << "Total runtime: " << X << " seconds" << endl;

where X is a double.

Stacks, Queues, and the STL

While you are free to implement your own stack and queue classes, you are encouraged to use the STL's implementations. This will save you some programming time and most likely decrease the overall runtime of your program (STL containers have been highly optimized over several years). Helpful links on the STL can be found at SGI STL Reference (official) and cppreference.

Command Line Arguments

Your program needs to support the following command line arguments: (a switch is set if it appears on the command line)

--Stack (boolean) If this switch is set, use the stack-based approach
--Queue (boolean) If this switch is set, use the queue-based approach
--Opt (boolean) If this switch is set, find the shortest path
--Time (boolean) If this switch is set, print the runtime of the program as described above.
--Incoordinate (boolean) If this switch is set, the input file is in the coordinate-based system. If the switch is not set, the input file is in the text-map format.
--Outcoordinate (boolean) If this switch is set, the output file is in the coordinate-based system. If the switch is not set, the output file is in the text-map format.
--Help (boolean) If this switch is set, print out a brief, informative message on what your program is suppose to do, including what the switches are and what they do. Your program should then exit(0).

Legal command line inputs must include exactly one of --Stack, --Queue, or --Opt. If none or more than one option is specified, print out an informative error message to stdout and then exit(1). In order to help with input parsing, try using getopt or getopt_long functions. More information is found at http://www.gnu.org/s/libc/manual/html_node/Getopt.html. Note that you do not have to use getopt and getopt_long to do input parsing. You are free to use whichever method you prefer, so long as your code can parse the command line options.

Sample Inputs and Outputs

Using the stack-based approach with the text-map format for input and output, given:

4 5
@K@@@
@..@.
@@.@@
@@C@.

should result in:

4 5
@K@@@
@++@.
@@+@@
@@C@.

Using the queue-based approach with the coordinate-based format for input and output, given:

should result in:

Errors to Check For

In the text-map format, you should check for:
- illegal characters
- maps that are incomplete (not enough characters/line or not enough lines)
- files that don't start with a pair of positive numbers as the first line
In the coordinate-based format, you should check for:
- illegal characters in the first column
- coordinates that don't fit inside the maze
- files that don't start with a pair of positive numbers as the first line
Not having exactly one of --Stack, --Queue, or --Opt switches set

In all cases, print an informative error message to standard error (stderr) and exit(1).

Errors Not to Check For

In the text-map format, ignore all extra characters on a given line, or on lines below the last line needed.
In the coordinate-based format, assume the character format is correct, i.e., char int int. However, you do need to check if the character and integers are valid.

Testing Your Program

Testing your code to see if it produces the correct solution is essential. We highly recommend that you test your code thoroughly with test cases beyond what we have given. For instance, your code may have a bug that the given examples do not uncover or your code works with a 5x5 grid but not a 10x10. Thus, in addition to your code, you must also submit 10 additional test mazes. Try to have a variety of mazes to make sure that your code is robust and does not have hidden bugs. For example, have small-, medium-, and large-sized maze grids, mazes that are long or wide, and maze that are sparsely-populated (very few obstacles) and densely-populated (many obstacles). Store all your tests in subdirectory called TEST. Each test should be named test[number], where [number] is between 01 and 10.

Sample Runs of the Program

The following shows two examples of what your program should print. Note: your program should use cin when reading in the input. The notation of < test01.txt is file input redirection and NOT reading in from a file called "test01.txt". Therefore, your code should not use ifstream for input and only use cin. To learn more about file redirection, visit http://en.wikipedia.org/wiki/Redirection_%28computing%29#Redirecting_standard_input_and_standard_output.

Run #1

The file test01.txt contains a standard text-map format of a maze that looks like:

4 5
@K@@@
@..@.
@@.@@
@@C@.

%> ./KirbysMaze --Stack < test01.txt

Welcome to Kirby's Quest for Cake!
Approach:         Stack-based
Runtime reported? No
Input format:     Text-map

Solution:
4 5
@K@@@
@++@.
@@+@@
@@C@.

Kirby thanks for you for finding the piece of cake.
%>

Run #2

The file test02.txt contains a standard coordinate-based format of a maze:

% ./KirbysMaze --Queue --Time --Incoordinate < test02.txt
Welcome to Kirby's Quest for Cake!
Approach:         Queue-based
Runtime reported? Yes
Input format:     Coordinate-map

Solution:
+ 3 8
+ 3 9
+ 4 9
+ 5 9
+ 5 8
+ 5 7
+ 6 7
+ 7 7

Total runtime: 0.354 seconds

Kirby thanks you for finding the piece of cake.
%>

How to Submit Your Project

You can start making submissions to the autograder once you think your program works. The autograder will test your program on its own set of test cases (not necessarily the same ones used for grading) and then report the results back to you. Some of the test cases will be available for you to see, some will not. We highly recommend you start making trial submissions at least one week before the deadline so you can work bugs out. Keep in mind that the autograder is on a Red Hat Linux machine (same as the CAEN machines). Although all the code should compile and work on any system, sometimes weird things happen. Thus, we recommend that you test and compile (and develop) your code in Linux on the CAEN machines and not in Windows. Do all of your project work with all needed files in some directory other than your home directory. This will be your "submit directory". When you are ready to submit your final version, make sure:

you have deleted all .o files and all executable(s) and that typing make clean accomplishes this
your makefile is called Makefile
typing the command make will result in an executable called KirbysMaze
your 10 test cases are in the TEST folder
you have no other files besides what you need
Your code compiles and runs correction using version 4.1.2 of the g++ compiler. This is the standard version on the CAEN Linux systems (such as login.engin.umich.edu). Even if everything seems to work on another operating system or with different versions of GCC, the course staff will not support anything other than GCC 4.1.2 running on Linux.

Turn in the following files:

all your .h and .cpp or .cc files
Makefile
the 10 test cases in the TEST subdirectory
Design Plan (submit separately - see below)

You must prepare a compressed tar archive (a .tar.gz file) of all of your files to submit to the autograder. One way to do this is to have all of your files for submission (and nothing else) in one directory. Go into this directory and run this command:
tar czf ../filename.tar.gz *
This will prepare a suitable file in the parent of your working directory. Submit your tar ball directly to the autograder at: https://grader8.eecs.umich.edu.

You may submit up to 3 times a calendar day to autograder for feedback. For this purpose, a calendar day begins at midnight (12:00:00am) and ends at 11:59:59pm Ann Arbor local time. If you submit more than 3 times, the autograder will acknowledge that you have submitted but will not provide you with feedback. The program will verify that you want to submit your code. After you accept, you will receive some feedback stating that you have submitted your code. If you do not receive feedback within 30 minutes, do not panic. Keep in mind that feedback can be delayed, especially if it's two hours (or fewer) before the official project deadline. If you have any problems with the autograder, email Mark Gordon at msgsss@umich.edu. Thus, if possible, submit early!

Coding Style

Your code will be mostly evaluated by a program called BackSeatCoder, developed by one of Professor Markov's students. The coding style feedback will be included in the autograder's feedback. Your style will be graded on what warnings it gives you (and how many) and a hand-grading of the code. Some suggestions to improve your score:

Use a reasonable structure for your program:
- Find a fairly reasonable class structure.
- Don't lump everything into one class.
- Make use of constructors and destructors (like when deallocating memory).
- Use multiple .cpp and .h files as appropriate. For example, class declaractions should go into the header files (.h) and their subroutines should go into standard code files (.cpp).
- In general, if your code seems sloppy to you, then it probably is. Try and write code that you and others can understand.
Use informative and concise comments:
- Explain what each class does what each of its member functions do.
- A 1-2 line explanation is useful for non-standard coding syntax.
- List your name and date modified for each file.
- A useless is comment is worse than no comment at all. For example,
```
 int temp; // creates temp variable 
```
  is not helpful.
Formatting your code:
- Use indentations when you have if/for/while/general code blocks.
- Avoid going past 80 characters per line.
Variable names:
- Use reasonable and informative names.
- Using variables "i" and "j" are acceptable for LCVs (loop control variables), but consider using other names for long-term data.
Code reuse: this is one section where poor style might result in poor design. For example, the stack- and queue-based implementations are almost identical with the exception of the data structure used. See if you can find a way to implement the structure such that a data structure can be "plugged in" according to the command line switches.

Memory Usage

For all three approaches, you are allowed an additional O(N) amount of memory.

Runtime Evaluation

Your final project grade will be based partially on the total runtime of the search algorithm (see below). Ten points will be allocated for this. Five points will be available for code that can complete the hardest benchmarks within a reasonable amount of time (10 second timeout). The autograder can give you a good indication of this. Five additional points will be awarded for completing the test cases quickly (competitive runtime), independent for each test case. provided that you have passed all the test cases.

Design Plan

By 11:59:59pm on September 28th, 2009, you must fill out a design plan (available on CTools) which will detail your plans for this project. Five points of your grade will be available for the design plan. Fill out the plan, and then create the file design.tar.gz (tar czf design.tar.gz design.txt) and submit it to the autograder. You can name the tar ball whatever you prefer, but make sure that your design plan is called design.txt. (https://grader8.eecs.umich.edu). In your submitted design plan, all the prompts originally in the document must remain there. Your answers should begin on a new line but not begin with a '@' symbol.

Grading

The grading for Project 1 is out of 100 points:

55 points - A working (passing all testcases) stack- and queue-based implementation of the program.
10 points - A working (passing all testcases) optimal path implementation of the program.
10 points - Coding style.
5 points - Completing all test cases under a reasonable amount of time.
5 points - Completing all test cases under a competitive amount of time (assuming you have the first 5 points)
5 points - Submission of 10 (personally constructed) test cases.
5 points - Design plan.

Submission Time and Late Policy

The project is officially due at 06:00:00pm on Friday, October 2nd, 2009. However, the submission server will stay online until approx. 11:45pm. Keep in mind, though, after 6pm, the support, e.g., phorum responses, may be limited.

As mentioned in class, you will have one "free" late day for all of the projects. That is, you are allowed to continue submitting for another 24 hours after the server is officially turned off. You are free to use this one day any time you wish, including for this project. If you are submitting past the deadline, contact the teaching staff so we are aware of this.

Extra Credit

20 points of extra credit are available for this project. You should not work on this until you have Project 1 fully operational. Any credit received from this portion will not affect the curve for the class, just your overall position. That is, the mean and standard deviation for the class will be calcuated without these points and then your score will have these points added on separately. The assignment is an extension to the optimal path finding problem. Instead of leading Kirby to one piece of cake, you will keep trying 'til you run out of cake. Each additional piece of cake will be represented with another C on the text-map or another line in the coordinate-based system. For this problem, you must find a path that covers the least amount of blank spaces. That is, you are allowed to backtrack without penalty (single pieces of cake help Kirby's memory but not overall endurance). For example, consider the following maze:

6 10
@@@C@@@@@@
@@@......@
@@.....C@.
@...@@@@@@
@K..@.....
@@@@@.....

In the same format, the optimal path in this maze would be:

6 10
@@@C@@@@@@
@@@+.....@
@@.++++C@.
@..+@@@@@@
@K++@.....
@@@@@.....

Note that even though there is some backtracking, the total number of spaces taken up is 8. The number of pieces of cake can be arbitrary (but at least 2) along with the size of the maze. Your only hard constraints will be a reasonable time limit and the correctness of the route produced. Some partial credit will be avaiable, but only for solutions that are very close to the optimal in all cases. In your Makefile, include an executable called KirbysFeast as well as KirbysMaze.

Runtime Limit

Given N pieces of cake available in the maze, your runtime must be upperbounded by 3*N*(time of the optimal path generator for one piece of cake).

Hints and Advice

Start early! The earlier you start, the more questions you'll be able to ask.
Print debugging statements to standard output as you develop your program. Just remember to remove/silence them before you submit your final version.
Good luck!